﻿#pragma once

namespace bit {
	template<class T>
	struct list_node { //节点结构体。
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;

		list_node(const T& x = T())//如果T是自定义类型，则x会是该类型的默认构造对象，取决于该类型的默认构造函数如何定义。
			:_data(x), _next(nullptr), _prev(nullptr) {
		}

		//为右值引用提供一个构造函数，不能带缺省参数，否则调用歧义
		list_node(T&& x)
			//:_data(move(x)), _next(nullptr), _prev(nullptr) {
			:_data(forward<T>(x)), _next(nullptr), _prev(nullptr) {
		}
	};


	template<class T, class Ref, class Ptr>//迭代器是模拟指针的行为
	struct __list_iterator { //迭代器
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;
		Node* _node;

		//迭代器可以理解为节点指针
		__list_iterator(Node* node)//单参数构造函数支持隐式类型转换，也就是说节点指针也可以隐式类型转换为迭代器
			:_node(node) {
		}

		self& operator++() { //前置++
			_node = _node->_next;
			return *this;
		}
		self& operator--() { //前置--
			_node = _node->_prev;
			return *this;
		}

		self operator++(int) { //后置++
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		self operator--(int) { //后置--
			self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

		Ref operator*() { return _node->_data; }
		Ptr operator->() { return &_node->_data; }//提供给自定义类型解引用。自定义类型解引用是 指针->形式，所以返回指针
		//非const和const迭代器中只有上面这两个运算符重载的返回值不同
		bool operator!= (const self& s) { return _node != s._node; }
		bool operator== (const self& s) { return _node == s._node; }
	};


	template<class T>
	class list {
		typedef list_node<T> Node;
	public:
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;

		const_iterator begin() const { return _head->_next; }//支持隐式类型转换
		const_iterator end() const { return _head; }//支持隐式类型转换
		iterator begin() { return _head->_next; }
		iterator end() { return _head; }

		void empty_init() {
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}

		list() { empty_init(); } //构造函数本质是创建一个哨兵位节点

		//lt2(lt1)
		list(const list<T>& lt) { //lt是const对象，需要const迭代器
			empty_init();//创建(lt2的)哨兵位
			for (auto e : lt)//遍历lt1每个节点赋值给e
				push_back(e);//lt2尾插每个e节点
		}

		//现代写法
		void swap(list<T>& lt) {
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}
		list<T>& operator=(list<T> lt) {
			swap(lt);
			return *this;
		}

		~list() {
			clear();
			delete _head;//清除哨兵位
			_head = nullptr;
		}

		void clear() {
			iterator it = begin();//begin指向哨兵位的下一节点，即有效数据的头节点
			while (it != end())
				it = erase(it);
		}

		void push_back(const T& x) { insert(end(), x); }//end指向哨兵位，在哨兵位之前插入
		//void push_back(T&& x) { insert(end(), x); }//右值引用版本
		//void push_back(T&& x) { insert(end(), move(x)); }
		////右值被右值引用 引用后的属性是左值，这样insert时走的就是左值引用版本
		////所以move改变x的属性为右值
		void push_back(T&& x) { insert(end(), forward<T>(x)); }

		void push_front(const T& x) { insert(begin(), x); }
		void pop_back() { erase(--end()); }//哨兵位前一节点就是尾结点
		void pop_front() { erase(begin()); }

		iterator insert(iterator pos, const T& x) {
			Node* cur = pos._node;
			Node* newnode = new Node(x);
			Node* prev = cur->_prev;
			//prev newnode cur
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			++_size;
			return iterator(newnode);
		}

		iterator insert(iterator pos, T&& x) {
			Node* cur = pos._node;
			//Node* newnode = new Node(move(x));//右值引用版本
			//这里和push_back同理，右值被右值引用 引用后的属性是左值
			//这样走的就是左值引用版本的构造函数，所以move改变x的属性为右值
			Node* newnode = new Node(forward<T>(x));
			Node* prev = cur->_prev;
			//prev newnode cur
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			++_size;
			return iterator(newnode);
		}

		iterator erase(iterator pos) { //erase后迭代器失效，因为迭代器指向的节点被释放了，所以返回下一个节点的位置
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			delete cur;
			prev->_next = next;
			next->_prev = prev;
			--_size;
			return iterator(next);
		}

		size_t size() { return _size; }

	private:
		Node* _head;
		size_t _size;//增加该成员避免每次获取size都要遍历一遍链表
	};
}